Abd al-Rahman ibn Habib merupakan cicit Uqba bin Nafi al-Fihri (Arab Muslim yang menakluk Afrika Utara). Keluarganya, al-Fihri, merupakan satu daripada keluarga Arab utama di Afrika Utara atau Maghreb.

Pada tahun 740 M, beliau bersama-sama dengan bapanya, Habib bin Abi Ubaidah (atau dieja Habib ibn Abi Obeida) dalam satu ekspedisi Arab yang merentasi laut ke Sicily dalam apa yang merupakan cubaan pertama untuk menyerang pulau itu secara besar-besaran (berbanding dengan pencerobohan kecil). Merka mendarat dengan selamat dan buat mengepung kota Syracuse buat seketika sehingga kota itu bersetuju untuk membayar ufti. Walau bagamanapun Pemberontakan Berber di Maghreb memaksa puak al-Fihris untuk membatalkan serangan terhadap Sicily dan bergegas pulang ke Afrika bagi mengangani pemberontakan tersebut. Orang Arab ditewaskan oleh Berber pada Pertempuran Baqdura (berdekatan Sebou) (741 M). Abdul Rahman bin Habib hampir terbunuh sementara bapanya maut di medan pertempuran. Abdul Rahman melarikan diri bersama-sama saki baki tentera Arabnya dengan menyeberangi selat ke Sepanyol.